package main

import (
	"fmt"
	"sort"
)

/**
执行用时：24 ms, 在所有 Go 提交中击败了58.79%的用户
内存消耗：7.6 MB, 在所有 Go 提交中击败了89.24%的用户
 */
func groupAnagrams(strs []string) [][]string {

	hash := make(map[string][]string)
	for _, str := range strs {
		s := sort_string(str)
		hash[s] = append(hash[s], str)
	}

	res := [][]string{}
	for key := range hash {
		res = append(res, hash[key])
	}
	return res
}

// 字符串排序，返回排序后的字符串
/****************************************/
type sortRunes []rune

func (s sortRunes) Len() int {
	return len(s)
}

func (s sortRunes) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func sort_string(s string) string {

	t := []rune(s)
	sort.Sort(sortRunes(t))

	return string(t)
}
/****************************************/

func main() {

	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Println(groupAnagrams(strs))
}
